Lab 5: Sharded Key/Value Service

课程网站，实验网站，实验指南。

Part A: The Controller and Static Sharding

实现

基本上就是复制 lab4 的代码，实现平衡分片到服务器的代码会花点时间，像在做算法题。

测试

使用命令 time go test -race -run 5A -count 1 -failfast -timeout 0 开始测试：

① 测试 TestMulti，报错 test_test.go:61: Shards wrong。日志显示，不同状态机的 Shards 数组包含相同的元素，但是顺序不同。可以想到，错误原因在于改变状态机的代码是非确定性的，由于提示中有说 map 遍历顺序的不确定性，所以我们可以很快定位错误。要使遍历顺序具有确定性，只好将 map 中的键放在数组中，排序之后遍历。

Part B: Shard Movement

实现

假设副本组 G1 负责的分片 S1 需要移动到副本组 G2。在 G1 发送分片之后，以及 G2 接收分片之前，都不应该处理和该分片相关的客户端请求，不论是新收到的请求还是已经在 applyCh 中的请求。G1 应该返回 ErrWrongGroup，G2 应该使用条件变量等待分片的到达。和 lab4 相同，如果服务器发现其已经不是 leader，则不应该继续等待。而且，G2 必须将接收的分片使用 Raft 应用到状态机之后，才能返回响应。为了方便的发送和删除分片，服务器应该按分片来存储数据。如果服务器需要发送多个分片，可以简单地串行发送，更好的做法是，并发地向不同副本组发送分片，在单个 RPC 中包含所有需要发向该副本组的分片。

如果在 G2 更新配置之前，G1 发送的分片到达 G2，该如何处理？在请求中应该包含配置编号，如果 G2 发现更大的配置编号，则使用条件变量等待配置更新，再处理该请求。如果 G1 发生故障，G2 可能会收到重复的分片，在将分片应用到状态机之前，应该限制该分片所属的配置编号和当前配置相同，并且使用副本组编号和配置编号的组合来去重。如果分片的配置编号小于当前配置编号，则直接响应 OK。

对于客户端请求，必须实现跨副本组的重复检测。例如，副本组 G1 已执行客户端的请求但未响应，然后 G1 向 G2 发送分片，最终客户端会向 G2 发送重复的请求。简单的解决方案是，G1 不仅发送分片，还发送用于重复检测的数据，所以重复检测的数据最好也是按照分片来存储。

服务器需要定期检查配置是否变更，在一个副本组中，只有 leader 会检查，还是所有副本都会检查？应该是只有 leader 检查配置变更，然后使用 Raft 将变更复制到其他副本中。因为不同副本检查配置变更的时机不同，服务器拒绝 applyCh 中相关请求的时机也就不同，从而状态机会不一致。在将配置变更应用到状态机之后，才开始发送分片，从而确保不同副本都会发送相同的分片。

在检查配置变更时，需要根据配置编号获取下一个配置，而不能直接获取最新配置，因为在未检查期间配置可能变更多次。如果 Raft 选举出新的 leader，它会检查下一个配置变更将其添加到日志，若此时通道中已经存在旧 leader 提交的一个/多个配置变更的日志，有可能会导致不正确的覆盖。所以，在将变更应用到状态机之前，应该总是限制配置编号是单调递增的。

配置必须线性地变更，如果配置变更多次，之后的变更必须等待之前的变更完成。可以将等待发送和接收的分片记录到状态中，然后使用条件变量检查状态来确定之前的配置是否完成。特别的，如果配置的编号为 1，则不需要记录状态。如果 leader 在变更配置的过程中崩溃，新的 leader 需要知道当前配置是否变更完成，所以上述状态应该使用 Raft 复制到副本中。同时，创建一个线程定期检查（或者使用条件变量），如果当前服务器是 leader，则发送状态中记录的待发送分片，发送完成之后删除对应分片。

测试

使用命令 time go test -race -run 5B -count 1 -failfast -timeout 0 开始测试：

① 在将配置应用到状态机之后，没有拒绝 applyCh 中的相关请求。 ② 在处理发送分片的 RPC 的响应时，忘记检查假设，需要确保当前配置编号和发送 RPC 时相同。 ③ 读取快照的语句放在初始化之前，导致错误的状态。 ④ Op 中的 map 会和 Raft 的 e.Encode(rf.log) 竞争，所以总是使用 map 的副本。 ⑤ 在修改状态时，没有唤醒条件变量。 ⑥ 有些状态只有 leader 会修改，所以 follower 需要特殊处理。

⑦ 如果 leader 接收分片，使用 Raft 复制到多数副本，在返回响应之后所有副本都崩溃。重启之后，由于 Raft 对提交之前任期的日志条目存在限制，该日志无法提交。此时，客户端请求该分片的数据将会阻塞直到日志应用，而日志无法提交除非在当前任期提交一个日志。解决方案就是，在重启之后总是添加一个空日志条目，来推进 commitIndex。之前测试有发生过低概率的报错，我当时就怀疑是 Raft 的实现有问题。

总结

Part B 有点折磨，有些很蠢的错误，花费很长时间才定位到。例如 ⑥，主要是太相信某个部分不会出错，结果就是那个地方有问题。例如 ①，以为已经实现某个功能，实际上存在遗漏，在定位错误时就不会往那个方面想。原因在于，没有在完成部分功能时做相关的测试，从而将发现错误的时间延后，此时代码已经有很多其他逻辑，定位错误会更加困难。错误 ②③④⑤ 是细节上的遗漏，因为功能实现并不是线性的过程，添加某个功能会修改已经实现的部分，逻辑交互在一起难免会有遗漏，特别是在代码组织很糟糕的情况下。整体来说，程序的并发运行会产生意想不到的交错，特别是存在网络或者机器故障的情况下，真的很难在最开始就写出正确的代码。